import java.util.*;

class KnapSack01
{
 double x[][];
 int size;
 double sackCap;
 public KnapSack01()
 {
  Scanner src=new Scanner(System.in);
  System.out.println("Enter the number of items");
  size=src.nextInt();
  x=new double[size][3];
  System.out.println("Enter the profits and weights");
  for (int i=0; i<size; i++)
  {
   x[i][0]=src.nextDouble();
   x[i][1]=src.nextDouble();
   x[i][2]=x[i][0]/x[i][1];
  }
  System.out.println("Enter the capacity of the sack");
  sackCap=src.nextDouble();
 }

 public void sort()
 {
  for (int i=0; i<size-1; i++)
    for (int j=0; j<size-1; j++)
      if (x[j][2]<x[j+1][2])
      {
       double t[];
       t=x[j];
       x[j]=x[j+1];
       x[j+1]=t;
      }
 }

 public void display()
 {
  System.out.println("The items are");
  for (int i=0; i<size; i++)
   System.out.println(x[i][0]+" -- "+x[i][1]+" = "+x[i][2]);
  System.out.println();
 }
 public void fillKnapSack()
 {
  
  double currentProfit=0, currentWeight=0;
  for (int i=0; i<size; i++)
  {
   if (currentWeight+x[i][1]<=sackCap)
   {
    currentWeight+=x[i][1];
    currentProfit+=x[i][0];
    System.out.println("Object "+(i+1)+" : "+x[i][0]+" -- "+x[i][1]);
   }
   if (currentWeight==sackCap)
     break;
  }
  System.out.println("Total Profit "+currentProfit);
  System.out.println("Total Weight "+currentWeight);
 }
}

class KnapSack
{
 public static void main(String args[])
 {
  KnapSack01 obj=new KnapSack01();
  obj.display();
  obj.sort();
  obj.display();
  obj.fillKnapSack();
 }
}

    
